//给你一棵二叉树的根节点 root ，二叉树中节点的值 互不相同 。另给你一个整数 start 。在第 0 分钟，感染 将会从值为 start 的节点开始爆发
//。 
//
// 每分钟，如果节点满足以下全部条件，就会被感染： 
//
// 
// 节点此前还没有感染。 
// 节点与一个已感染节点相邻。 
// 
//
// 返回感染整棵树需要的分钟数。 
//
// 
//
// 示例 1： 
// 输入：root = [1,5,3,null,4,10,6,9,2], start = 3
//输出：4
//解释：节点按以下过程被感染：
//- 第 0 分钟：节点 3
//- 第 1 分钟：节点 1、10、6
//- 第 2 分钟：节点5
//- 第 3 分钟：节点 4
//- 第 4 分钟：节点 9 和 2
//感染整棵树需要 4 分钟，所以返回 4 。
// 
//
// 示例 2： 
// 输入：root = [1], start = 1
//输出：0
//解释：第 0 分钟，树中唯一一个节点处于感染状态，返回 0 。
// 
//
// 
//
// 提示： 
//
// 
// 树中节点的数目在范围 [1, 10⁵] 内 
// 1 <= Node.val <= 10⁵ 
// 每个节点的值 互不相同 
// 树中必定存在值为 start 的节点 
// 
//
// Related Topics 树 深度优先搜索 广度优先搜索 二叉树 👍 51 👎 0


package leetcode.editor.cn;

// [2385]感染二叉树需要的总时间


import com.sun.corba.se.impl.orbutil.graph.Graph;

import javax.lang.model.element.VariableElement;
import java.text.DateFormatSymbols;
import java.util.*;

public class AmountOfTimeForBinaryTreeToBeInfected_2385 {
    private static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }

        public static TreeNode getRootNode() {
            return new TreeNode();
        }
    }

    public static void main(String[] args) {
        Solution solution = new AmountOfTimeForBinaryTreeToBeInfected_2385().new Solution();
        TreeNode root = TreeNode.getRootNode();
        root.val = 1;
        root.right = new TreeNode(2, null, new TreeNode(3, null, new TreeNode(4, null, new TreeNode(5))));
        System.out.println(solution.amountOfTime(root, 2));
    }
    //leetcode submit region begin(Prohibit modification and deletion)

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */


    class Solution {
        public HashMap<Integer, List<Integer>> map = new HashMap<>();

        public int amountOfTime(TreeNode root, int start) {
            dfs(root);
            Queue<Integer> queue = new LinkedList<>();
            queue.add(start);
            int ans = -1;
            HashSet<Integer> visited = new HashSet<>();
            visited.add(start);
            while (!queue.isEmpty()) {
                int size = queue.size();
                while ((size--) > 0) {
                    Integer poll = queue.poll();
                    List<Integer> list = map.get(poll);
                    if (list != null) {
                        for (Integer next : list) {
                            if (!visited.contains(next)) {
                                queue.add(next);
                                visited.add(next);
                            }
                        }
                    }
                }
                ans++;
            }
            return ans;
        }

        public void dfs(TreeNode treeNode) {
            if (treeNode == null) {
                return;
            }
            if (treeNode.left != null) {
                List<Integer> list = map.getOrDefault(treeNode.val, new ArrayList<>());
                list.add(treeNode.left.val);
                map.put(treeNode.val, list);
                list = map.getOrDefault(treeNode.left.val, new ArrayList<>());
                list.add(treeNode.val);
                map.put(treeNode.left.val, list);
            }
            if (treeNode.right != null) {
                List<Integer> list = map.getOrDefault(treeNode.val, new ArrayList<>());
                list.add(treeNode.right.val);
                map.put(treeNode.val, list);
                list = map.getOrDefault(treeNode.right.val, new ArrayList<>());
                list.add(treeNode.val);
                map.put(treeNode.right.val, list);
            }
            dfs(treeNode.left);
            dfs(treeNode.right);
        }
    }
//leetcode submit region end(Prohibit modification and deletion)


    class Node<T> {
        public T value;//值
        public int in;//入度
        public int out;//出度
        public ArrayList<Node<T>> nexts;//从自己连出去的下一个节点列表
        public ArrayList<Edge<T>> edges;//从自己连出去的边

        public Node(T value) {
            this.value = value;
            this.in = 0;
            this.out = 0;
            this.nexts = new ArrayList<>();
            this.edges = new ArrayList<>();
        }

        public void linkTo(Node<T> node) {
            linkTo(node, 1);
        }

        public void linkTo(Node<T> node, int weight) {
            this.nexts.add(node);
            this.out++;
            node.in++;
            this.edges.add(new Edge(weight, this, node));
        }

        public void link(Node<T> node) {
            linkTo(node);
            node.linkTo(this);
        }

        public void link(Node<T> node, int weight) {
            linkTo(node, weight);
            node.linkTo(this, weight);
        }

    }

    class Edge<T> {
        public int weight;//权重
        public Node<T> from;//来源
        public Node<T> to;//目的地

        public Edge(int weight, Node<T> from, Node<T> to) {
            this.weight = weight;
            this.from = from;
            this.to = to;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (o == null || getClass() != o.getClass()) {
                return false;
            }
            Edge<?> edge = (Edge<?>) o;
            return weight == edge.weight && Objects.equals(from, edge.from) && Objects.equals(to, edge.to);
        }

        @Override
        public int hashCode() {
            return Objects.hash(weight, from, to);
        }
    }

    class Graph<T> {
        public HashMap<Integer, Node<T>> nodes;//节点列表
        public HashSet<Edge<T>> edges;//边界列表

        public Graph() {
            nodes = new HashMap<>();
            edges = new HashSet<>();
        }
    }


    class Solution2 {
        Graph<TreeNode> graph = new Graph<>();

        public int amountOfTime(TreeNode root, int start) {
            makeGraph(root);
            Node<TreeNode> startNode = graph.nodes.get(start);
            if (startNode == null) {
                return 0;
            }
            Queue<Node<TreeNode>> queue = new LinkedList<>();
            HashSet<Node<TreeNode>> set = new HashSet<>();
            queue.add(startNode);
            set.add(startNode);
            int count = 1;
            int layer = 0;
            int sum = 0;
            while (!queue.isEmpty() && count > 0) {
                Node<TreeNode> cur = queue.poll();
                count--;
                for (Node<TreeNode> next : cur.nexts) {
                    if (!set.contains(next)) {
                        queue.add(next);
                        set.add(next);
                        sum++;
                    }
                }
                if (count == 0) {
                    layer++;
                    count += sum;
                    sum = 0;
                }
            }
            return layer - 1;
        }

        public void makeGraph(TreeNode treeNode) {
            if (treeNode == null) {
                return;
            }
            Queue<Node<TreeNode>> queue = new LinkedList<>();
            Node<TreeNode> node = new Node<>(treeNode);
            queue.add(node);
            graph.nodes.put(treeNode.val, node);
            while (!queue.isEmpty()) {
                Node<TreeNode> cur = queue.poll();
                if (cur.value.left != null) {
                    Node<TreeNode> left = new Node<>(cur.value.left);
                    cur.link(left);
                    queue.add(left);
                    graph.nodes.put(left.value.val, left);
                }
                if (cur.value.right != null) {
                    Node<TreeNode> right = new Node<>(cur.value.right);
                    cur.link(right);
                    queue.add(right);
                    graph.nodes.put(right.value.val, right);
                }
            }
        }
    }


    class Solution1 {
        int depth = -1;
        int ans = 0;

        public int amountOfTime(TreeNode root, int start) {
            process(root, 0, start);
            return ans;
        }

        public int process(TreeNode node, int level, int start) {
            if (node == null) {
                return 0;
            }
            if (node.val == start) {
                depth = level;
            }
            int leftHight = process(node.left, level + 1, start);

            boolean inLeft = depth != -1;

            int rightHight = process(node.right, level + 1, start);
            if (node.val == start) {
                ans = Math.max(leftHight, rightHight);
            }
            ans = Math.max(depth + (inLeft ? rightHight : leftHight) - level, ans);
            return Math.max(leftHight, rightHight) + 1;
        }
    }
}